package main

import (
	"fmt"
)

func main() {
	check()
}

func getLargest(s string) string {
	res := ""
	b := []byte(s)
	bi := 0
	for {
	label:
		if bi == len(b) {
			break
		}
		for i := byte('z'); i >= byte('a'); i-- {
			for j := bi; j < len(b); j++ {
				if b[j] == i {
					res += string(i)
					bi = j + 1
					goto label
				}
			}
		}
	}
	return res
}

type iotype struct {
	arg, result string
}

func check() {
	tests := []iotype{
		iotype{"test", "tt"},
		iotype{"a", "a"},
		iotype{"example", "xple"},
		iotype{"aquickbrownfoxjumpsoverthelazydog", "zyog"},
		iotype{"zzyyxxwwvvuuttssrrqqppoonnmmllkkjjiihhggffeeddccaa", "zzyyxxwwvvuuttssrrqqppoonnmmllkkjjiihhggffeeddccaa"},
		iotype{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"},
		iotype{"dtbsthudhqvqxxmqxusna", "xxxusna"},
		iotype{"ddifmyqoojkeyiee", "yyiee"},
		iotype{"mhdsrshovdancelcihqcrsfdfvsrgstsxvzh", "zh"},
		iotype{"vslheaxwhc", "xwhc"},
		iotype{"lumguibrvvnvwnwhzail", "zl"},
		iotype{"hctiodxvzmllfgri", "zri"},
		iotype{"zjxhngujgnhlqpkfwuseqzcrxzjsltdekwoiklfgkywdpj", "zzzywpj"},
		iotype{"sw", "w"},
		iotype{"xpmjapuoeqouquzjnuyxzajdrn", "zzrn"},
		iotype{"rkkpfgidl", "rpl"},
		iotype{"phqhlsucxtebkyemlykfmzlznmopuhgvdambgpiglo", "zzvpo"},
		iotype{"bzslcgclmgzulhxdrhkogsbuofrjrapcdutisprkrvosug", "zzxvug"},
		iotype{"puluqyrejeyurtkeaufs", "yyuus"},
		iotype{"znm", "znm"},
		iotype{"nxaiqgj", "xqj"},
		iotype{"rsng", "sng"},
		iotype{"sxcpfwwyjsjfkrxpycnvcwvcnghwphpxrlfmcccvyppfr", "yyyr"},
		iotype{"ubvbsmbdayynthasljdikieqdjbnmr", "yytsr"},
		iotype{"dvypuukxnjiqwavhfsypfghhqhumbfznmjn", "znn"},
		iotype{"t", "t"},
		iotype{"lohyungouxtdkoqncecbecamiglwxamgkyjoisgymbeynmpftc", "yyyytc"},
		iotype{"mvcjkcbtzdyet", "zyt"},
		iotype{"zjejurusuqdatseyswqghs", "zyws"},
		iotype{"rkjqiepcwkgoobtawithjybepylvvwm", "yywm"},
		iotype{"sggqrxlcadkjjxcomhqgqpzkyetpz", "zz"},
		iotype{"oizojobmoeyncmosopractypj", "zyypj"},
		iotype{"qxydejwry", "yy"},
		iotype{"rnlrwcsgegebmwweybg", "yg"},
		iotype{"xbulkgnapqrb", "xurb"},
		iotype{"fqgq", "qq"},
		iotype{"euthsnsugfxtmfkwtlldwenybjfafvecasosvnxbs", "yxs"},
		iotype{"oxedpvevehtmfsletplcpnndvlxduxxwieibnthkhfnkpvhj", "xxxxwvj"},
		iotype{"akvccoziowkmrzpdwsvybiszfccgowzlosn", "zzzzsn"},
		iotype{"ixnaxxjgbmisqsjxjxgc", "xxxxxgc"},
		iotype{"i", "i"},
		iotype{"djouowzmqzafubqqenotqmwzfgcmtpveanvmb", "zzzvvmb"},
		iotype{"qparcaihdnyk", "yk"},
		iotype{"frraeazgnzdmhtbtaymysglanvdqlbmqicqw", "zzyyw"},
		iotype{"jeottiolzlxcy", "zy"},
		iotype{"gubnawecsnsekp", "wssp"},
		iotype{"uiktpzkdxynlifewoqmmbilpddlpecxndkebucbghbjqan", "zyxuqn"},
		iotype{"cjpxagblsqilexcqzjngqhnc", "zqnc"},
		iotype{"jvgloimmvsdhfgdafmzhxbzwfhkntrjpaocnidhfzeooqp", "zzzqp"},
		iotype{"mdvmgsxmxnvxgjtsheoxvmgoryhnkswbznzvfrdrqjm", "zzvrrqm"},
		iotype{"aanhrzdsbbhdoezohvuhzoeaekxpwhnj", "zzzxwnj"},
		iotype{"hhf", "hhf"},
		iotype{"onltutgmnnpxiwue", "xwue"},
		iotype{"ygng", "yng"},
		iotype{"sgrmksiyzesherusczthyotrbtzvegbzkulsprvikhohlyg", "zzzzyg"},
		iotype{"rgzoaitknjjioypjiaevejqldjgtw", "zyw"},
		iotype{"iynwupnztulzbyk", "zzyk"},
		iotype{"mrtnnhfvaqtctfuipndaye", "ye"},
		iotype{"zegbcvvxxfqxo", "zxxxo"},
		iotype{"kwpxplhnattmiuhdq", "xuq"},
		iotype{"zkhpjjfztbnxs", "zzxs"},
		iotype{"wdxxiqzyhhxsp", "zyxsp"},
		iotype{"egdnuvamuhkucdfvssxavdjuymvzgfymr", "zyr"},
		iotype{"kwjuffpavnbkypmtfuxvabwj", "yxwj"},
		iotype{"jbxoquxgeettykaciacheofaqceidc", "yqidc"},
		iotype{"pnmqqmkogrhghpqwcpzdspbtvlvpotgdikgm", "zvvtm"},
		iotype{"vwqmytncvpxazwrjwroacwono", "zwwwoo"},
		iotype{"oehulzriqbdtawyytjskhlemqmdshspq", "zyytsssq"},
		iotype{"mlwlasmlxqriipmqglsvswhnxyirhaofgyhkiwpo", "yywpo"},
		iotype{"eszpgnfapcsbftxagmmdcqi", "zxqi"},
		iotype{"rbjopthedsdewdudlupyicpmdtpmqrf", "ytrf"},
		iotype{"renwjvqjfdzywfxpajvemksbdb", "zyxvsdb"},
		iotype{"hnrthrdkyalotlymzcumobmvzvstciqmnbxdlgftjgpfbm", "zzxtpm"},
		iotype{"uzkbkzmdozxqmvvmbbioyljyemntpldykxwjgnllqrdugrahe", "zzzyyyxwurhe"},
		iotype{"tfhsnjkvbndnnqjkwfd", "wfd"},
		iotype{"iy", "y"},
		iotype{"zyeqfuqghbnhhrboymupudbomtlql", "zyyuutql"},
		iotype{"yougpkmhhdmkorkkincpcnhxunainwqhbmmxkhwfarlahdmoak", "yxxwrok"},
		iotype{"ljmlijlnlfaaynvqyhtxck", "yyxk"},
		iotype{"ezhidvylyuyqluoxozyv", "zzyv"},
		iotype{"kjqhcdshyfeqiwrencjowhqksyqeyeutemfgmyxs", "yyyyxs"},
		iotype{"ydikqgggygevjdeyxpnzvmdvfkxralhnuvywensvwe", "zywwe"},
		iotype{"rdpwejzcdxxcimwm", "zxxwm"},
		iotype{"jtlgzwjtyaewnvgezxcyntlj", "zzytlj"},
		iotype{"hjypqtcafblpnlxeaavswvaijkflyrekr", "yyrr"},
		iotype{"drmtfhglfcmsobeqibtjcskngttvmzzpgkvxwctv", "zzxwv"},
		iotype{"wvttsspponkjjihfebaa", "wvttsspponkjjihfebaa"},
		iotype{"xwssrplkihgfc", "xwssrplkihgfc"},
		iotype{"zzzyyyxwwvtronnlllljiiigeddccbbaa", "zzzyyyxwwvtronnlllljiiigeddccbbaa"},
		iotype{"l", "l"},
		iotype{"zxrrmfda", "zxrrmfda"},
		iotype{"xwwvvutttssqqpppoonnnmllkkkkjjjihhffccccbbbba", "xwwvvutttssqqpppoonnnmllkkkkjjjihhffccccbbbba"},
		iotype{"zyxuuuttttssqpoommmlkkjihgeeddccaaa", "zyxuuuttttssqpoommmlkkjihgeeddccaaa"},
		iotype{"yxwsssrllkc", "yxwsssrllkc"},
		iotype{"yvqqoollkca", "yvqqoollkca"},
		iotype{"zyutttsqqppponnnnnmlllkkkjihhhggeeeddccbbb", "zyutttsqqppponnnnnmlllkkkjihhhggeeeddccbbb"},
		iotype{"zxxvsrponmmljiiihgba", "zxxvsrponmmljiiihgba"},
		iotype{"xwvssqoljjjiiigfccbaa", "xwvssqoljjjiiigfccbaa"},
		iotype{"zzywwutsssrrronmllljjiihhgggggfeeea", "zzywwutsssrrronmllljjiihhgggggfeeea"},
		iotype{"wvsqonkifecb", "wvsqonkifecb"},
		iotype{"zzyyyxxwvvutssrrrqqppponmllkjjiihgffdcbbbaa", "zzyyyxxwvvutssrrrqqppponmllkjjiihgffdcbbbaa"},
		iotype{"zzywuuusssrrrqponmlkkkiigfedccb", "zzywuuusssrrrqponmlkkkiigfedccb"},
		iotype{"yyyyyyxxwwwvutttssrqqppppoonnmkjihgggddddaa", "yyyyyyxxwwwvutttssrqqppppoonnmkjihgggddddaa"},
		iotype{"zxooc", "zxooc"},
		iotype{"utqp", "utqp"},
		iotype{"yxuttssrrnmjida", "yxuttssrrnmjida"},
		iotype{"ffffeeeeeddddccccccccccbbbbbbbbaaa", "ffffeeeeeddddccccccccccbbbbbbbbaaa"},
		iotype{"ffeeedcccca", "ffeeedcccca"},
		iotype{"fdda", "fdda"},
		iotype{"ffffeeeeeeddddcccccccbbbbbbbaaaaaaaaa", "ffffeeeeeeddddcccccccbbbbbbbaaaaaaaaa"},
		iotype{"fffeeeeeddddddddcccccccbbbbbbbbbaaaa", "fffeeeeeddddddddcccccccbbbbbbbbbaaaa"},
		iotype{"ffffeeeeeedddccccccbbbaaaa", "ffffeeeeeedddccccccbbbaaaa"},
		iotype{"ffffffeeeeedddddddcccccccbbbbbbbbaaaaaaaa", "ffffffeeeeedddddddcccccccbbbbbbbbaaaaaaaa"},
		iotype{"ddba", "ddba"},
		iotype{"fffbbaaa", "fffbbaaa"},
		iotype{"fedddccccbbbaa", "fedddccccbbbaa"},
		iotype{"ffffeeeeeddbaaa", "ffffeeeeeddbaaa"},
		iotype{"fffffeeeeeeeeeeedddddcccccccccccbbbbbbbbbbbaaaaa", "fffffeeeeeeeeeeedddddcccccccccccbbbbbbbbbbbaaaaa"},
		iotype{"ffebbb", "ffebbb"},
		iotype{"ffeedddcbbbbaa", "ffeedddcbbbbaa"},
		iotype{"fffeeeeddccccbbbbbbbbaaaaaa", "fffeeeeddccccbbbbbbbbaaaaaa"},
		iotype{"bbbb", "bbbb"},
		iotype{"fffedaaaa", "fffedaaaa"},
		iotype{"bbaaaabaabbaabbbaaabbaaabaaabababaaababaaaabbbbba", "bbbbbbbbbbbbbbbbbbbbba"},
		iotype{"bbabbabbabaababaababaaaaaabaabab", "bbbbbbbbbbbbbb"},
		iotype{"abbbbabbbbbbabbbbabbababbabbabbba", "bbbbbbbbbbbbbbbbbbbbbbbba"},
		iotype{"bbbbbaabbaaabaabbababaabbababaabba", "bbbbbbbbbbbbbbbbbba"},
		iotype{"bbbabababbaa", "bbbbbbbaa"},
		iotype{"abbbbabbabbbabaaaaabaabaabaaababbbbabbb", "bbbbbbbbbbbbbbbbbbbbb"},
		iotype{"babbaaaa", "bbbaaaa"},
		iotype{"abbaabbaaaaabbbbbabbaaaaa", "bbbbbbbbbbbaaaaa"},
		iotype{"baaababbaaabbbabbaaaaababaaabaaaaa", "bbbbbbbbbbbbaaaaa"},
		iotype{"baabbaba", "bbbba"},
		iotype{"aedcbacdeacdedbebbc", "eeeec"},
		iotype{"caefdadbeedbebdcbcdca", "feeeddca"},
		iotype{"fbbabcccbbbbfcabf", "fff"},
		iotype{"ceaeedacaffddcfcdaebacdeeeb", "fffeeeeb"},
		iotype{"dcbecaded", "eed"},
		iotype{"ccddabecdfcbdefeedbbdaacda", "ffeeddda"},
		iotype{"dcffbbbbcfefedbbbfcdafddebfcdfdeeccfe", "fffffffffe"},
		iotype{"ffebcdbfccedbfaeaedaaaeefebdcdfa", "ffffffa"},
		iotype{"addcfafeaeefcbefcbbcedfbcfcdffcaaeeafdadcfca", "ffffffffffca"},
		iotype{"fcb", "fcb"},
		iotype{"fgfdsdgaasfdghfgffggffgfgf", "sshgggggf"},
		iotype{"asxcsa", "xsa"},
		iotype{"fhjtgui", "ui"},
		iotype{"naa", "naa"},
		iotype{"ttt", "ttt"},
		iotype{"maxbm", "xm"},
		iotype{"baaaf", "f"},
		iotype{"zba", "zba"},
		iotype{"zzzzzzzzzzddddddddddccccccccccbbbbbbbbbbaaaaaaaaaa", "zzzzzzzzzzddddddddddccccccccccbbbbbbbbbbaaaaaaaaaa"},
		iotype{"hhhhhhh", "hhhhhhh"},
		iotype{"tatttatttt", "tttttttt"},
		iotype{"aaaaaaaaa", "aaaaaaaaa"},
		iotype{"abcdefghgiabcdefghgiabcdefghgiabcdefghgiabcdefghgi", "iiiii"},
		iotype{"zzzzz", "zzzzz"},
		iotype{"aa", "aa"},
		iotype{"bza", "za"},
	}
	for _, t := range tests {
		a := getLargest(t.arg)
		if a == t.result {
			//fmt.Printf("OK\n")
		} else {
			fmt.Printf("NG return:%s expected:%s", a, t.result)
		}
	}
}

